A computer network is a geographically distributed collection of interconnected communication links and subnetworks (subnets) used to transport data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The nodes typically communicate by exchanging discrete packets or messages of data according to pre-defined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other. The TCP/IP architecture is well known and described in Computer Networks, 3rd Edition, by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
Computer networks may be further interconnected by an intermediate node, such as a router, to extend the effective “size” of each network. Since management of a large system of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as autonomous systems or routing domains. The networks within a routing domain are typically coupled together by conventional “intra-domain” routers. Yet is still may be desirable to increase the number of nodes capable of exchanging data; in this case, interdomain routers executing interdomain routing protocols are used to interconnect nodes of the various autonomous systems.
An example of an interdomain routing protocol is the Border Gateway Protocol version 4 (BGP-4), which performs routing between autonomous systems by exchanging routing and reachability information among neighboring interdomain routers of the systems. The BGP-4 routing protocol is well known and described in detail in Request For Comments (RFC) 1771, by Y. Rekhter and T. Li (1995), Internet Draft <draft-ietf-idr-bgp4-20.txt> titled, A Border Gateway Protocol 4 (BGP-4) by Y. Rekhter and T. Li (April 2003) and Interconnections, Bridges and Routers, by R. Perlman, published by Addison Wesley Publishing Company, at pages 323-329 (1992), all disclosures of which are hereby incorporated by reference.
The interdomain routers configured to execute the BGP-4 protocol, referred to herein as BGP routers, perform various routing functions including transmission of routing messages. An adjacency is a relationship formed between selected neighboring (peer) routers for the purpose of exchanging routing messages and abstracting the Network topology. Before transmitting such messages, however, the BGP peers cooperate to establish a logical “peer” connection (session) between the routers. BGP-4 operates over a TCP connection, a reliable transport protocol. A TCP process executing on each peer router establishes the TCP connection in accordance with a conventional “3-way hand-shake” arrangement involving the exchange of TCP packet or segment data structures. The TCP protocol and establishment of a TCP connection are described in Computer Networks, 3rd Edition, particularly at pgs. 521-542, which is hereby incorporated by reference as though fully set forth herein.
FIG. 1 is a partial schematic block diagram of the format of a TCP segment 100. The TCP segment comprises a TCP header 110 that includes a source port field 112 containing a 16-bit source port number and a destination port field 114 containing a 16-bit destination port number. The source port number is used by a receiving peer router (i.e., a BGP receiver) to reply to a TCP segment 100 issued by a sending peer router (i.e., a BGP sender). A sequence number field 116 contains a sequence number of a first data byte in the segment and an acknowledgement number field 118 contains a value indicating the next sequence number that the receiver expects to receive. Note that the value contained in field 118 is valid only when an acknowledgement control bit (ACK 120) is asserted. In addition to the ACK bit 120, the TCP segment 110 includes other control bits, such as a synchronize bit (SYN 122) and a finish bit (FIN 124), the latter denoting the end of data transmitted from the sender. Termination (closing) of the TCP connection is done explicitly by sending a TCP segment with an asserted FIN bit 124.
To establish a TCP connection, the TCP processes on the peer routers must synchronize on each other's initial sequence numbers. This is done in an exchange of connection establishing segments carrying the SYN 122 control bit and the initial sequence numbers 116. Synchronization requires each peer router to send its own initial sequence number and to receive a confirmation (acknowledgement) from the other peer router according to the 3-way handshake arrangement. The resulting TCP connection is identified by the port numbers contained in fields 112,114 and IP addresses of the peer routers. The IP addresses are contained in an IP header of the segment.
FIG. 2 is a partial schematic diagram of the format of an IP header 200 comprising, inter alia, a source address field 220 containing the IP source address of the sending entity (e.g., the sending or initiating peer router) and a destination address field 230 containing the IP destination address of the receiving entity (e.g., the receiving peer router). In addition, the IP header 200 includes an 8-bit time-to-live (TTL) field 210 that contains a parameter indicating a maximum time the segment (or message) is allowed to remain in the network. For many routing protocols, including protocols that run over unreliable transports or implement reliable transports other than TCP, the TTL parameter is set to 1 in the routing message. This implies that the neighbor is on the same subnet and that there is only one “hop” distance between the peer routers.
BGP routers typically transmit BGP messages with a TTL of 1 for all directly connected peers. For all incoming BGP messages, the TTL can then be checked to ensure that it is 0. That is, if a BGP router is communicating with a routing peer and the TTL of the message is set to 1, the TTL should be 0 (or 1) when it gets to the router because the message should not have traversed more than one router to other subnets. Note that the TTL is not always set to one for BGP, as the adjacency can span multiple “hops” (for multi-hop BGP). In that latter case, the TTL is set at 2, 3 or whatever the multiple hop count.
One problem is that an attack may be launched against the BGP router from several hops away to, e.g., overload the router with more data than it can handle. Often an authentication process on the router performs authentication (such as MD5 or IP-SEC) operations to ensure that the data it receives from its peer is correct. In the case of the BGP routing process, the TCP process authenticates the TCP header of a message. However, these authentication operations require extra processing and, thus, consume router resources, such as a central processor unit (CPU).
While it does protect invalid data from being sent, such extra processing exposes the router to further attacks by, e.g., allowing an attacker to send “bogus” messages. The authentication process is forced to authenticate these messages and discard them when they fail authentication. Yet, if the attacker sends the router more information than it can handle, the attacker may achieve its desired effect of forcing the router to reboot. That is, the bogus data message overload forces the router to reboot so that the attacker can penetrate the router or just disrupt service. In addition, the router may perform filtering operations to make sure that the TTL of a routing protocol message is 1 or 0 (and not some other value). Such filtering allows that router to quickly discard bogus messages, as it is easier to examine the value of the TTL field than having to do an encryption-type of authentication operation on the message to determine whether it is bogus.
However, an attacker from outside the subnet can send messages that the router will accept by, e.g., setting the TTL to a value consistent with the number of hops away it is from the router. The TTL field is decremented by one at each router that forwards the message. When the message arrives on that subnet/link, it looks like it originated on that link. In other words, the message received at the router will have the same TTL (e.g., one) as every other message originated by routers on that link. Thus, if an attacker is able to determine how many hops away it is from the router, it can successfully launch an attack against the router. The attacker may also spoof the source address in the IP header of the message so that it looks as if the message originated on the destination local subnet.
A solution to this problem is to set the TTL parameter to a high value, e.g., 254, in accordance with a BGP TTL Security Hack (BTSH). BTSH is well known and described in detail in Internet Draft <draft-gill-btsh-02.txt> titled, The BGP TTL Security Hack (BTSH) by V. Gill et al. (May 2003), which is hereby incorporated by reference as though fully set forth herein. BTSH is designed to protect the BGP [RFC 1771] infrastructure from CPU-utilization based attacks and, to that end, provides a procedure for protecting BGP routers from the attackers. For example, in the case of directly connected routers, the BTSH procedure specifies setting the TCP TTL for the BGP connection to a value in the range of 255-254.
When a routing peer receives the routing message, it checks the TTL field to ensure that, instead of a value of 0 or 1, the TTL value is not less than 254. This ensures that the message originated on the same subnet as the router and hasn't been forwarded from another subnet. This is similar to sending a message with a TTL of 1 and making sure that it is 0 at the receiving peer. Here, the TTL is sent with a value of 255 and the routing peer ensures that the value is 254 when received.
It is generally accepted that it is more secure to use BTSH (and a TTL of 255) for transmitted BGP routing messages. Accordingly, it is desirable that incoming BGP messages received at a BGP router have a TTL of 254 for directly connected peers. Attacks on the BGP router would likely have originated on the link that connects the peers in order to have a TTL of 254. If an attacker attacks a router from outside the subnet, it is difficult (if not impossible) to direct messages to the router with a TTL value of 254 because the maximum value of the TTL parameter that can be set by the attacker is 255. When the message is forwarded with that value from outside the subnet, it will have a value less than 254 when arriving at the router.
Multi-hop BGP can use the same method described above by only accepting messages with a TTL of 253 or less, with the value of the TTL parameter corresponding to the number of hops between BGP peers. Therefore, the router can be configured to discard (not accept) a message because of the TTL value. This solution greatly restricts where attacks on a router can originate; for example, such an attack may need to be launched from a site local to the subnet/link, which is generally difficult to achieve because the attacker has to be geographically in the general area as the router.
A problem with this solution involves upgrading the routers to support BTSH.
One way to upgrade a router is by “manual” configuration using, e.g., a conventional configuration command. Not only does the router require such manual configuration, but the router's peer(s) must also be configured to support BTSH at the same time. In particular, router configuration to support BTSH for BGP sessions generally occurs on a per-peer basis. Configuring the BTSH option on potentially thousands of peering sessions is time consuming and increases the possibility of configuration mismatches that prevent establishment of peering sessions. It is also difficult to coordinate the upgrade at the same time on both routers that are peers. A technique is thus needed to automatically detect whether a peer supports and is using the BTSH option.
Another way to upgrade is through a capabilities exchange between peer routers.
For example once a TCP connection is established, BGP peer routers exchange messages to open and confirm various parameters associated with the connection. An initial message exchanged by the BGP routers is an OPEN message that opens a BGP communication session between the peers. After the OPEN messages are exchanged, KEEPALIVE messages are issued periodically by a BGP router to notify its peer router that it is “alive” and active. The OPEN message data structure is essentially a means for the routers to identify themselves at the beginning of the neighboring peer relationship. The formats and functions of the KEEPALIVE and OPEN messages are described in RFC 1771 and Internet Draft <draft-ietf-idr-bgp4-20.txt>. 
In a typical capabilities exchange, a session must be established before any negotiation of capabilities ensues. For example since BGP runs over TCP, a TCP session has to be established before any routing protocol capabilities can be negotiated. It is generally difficult to negotiate a routing protocol capability, such as a TTL parameter, “within” the routing protocol after a session is established, because the session (procedure) has progressed too far. In this context, the term “within” a routing protocol denotes that there is a field (“behavior”) within the routing protocol message (packet) implementation that can be used. A technique “outside” of a routing protocol is thus needed to enable efficient capabilities negotiation before the routing protocol peering session is initiated.